#include <iostream>
#include <cassert>
#include "ST.h"
#include "TestSortHelper.h"
//基于无序链表的符号表

template <typename Key,typename Value>
class SequentialSearchST:public ST<Key,Value>{
private:
    struct Node{
        Key key;
        Value value;
        Node *next;

        Node(Key key, Value value){
            this->key=key;
            this->value=value;
        }

        Node(Key key, Value value, Node * nextNode){
            this->key=key;
            this->value=value;
            this->next = nextNode;
        }

    };

    Node* first;

    void destory(Node * node){
        if(node==NULL)
            return;
        destory(node->next);
        delete node;
    }

    Node* _get(Key key){
        for(Node* next = first;next!=NULL;next = next->next){
            if(next->key==key){
                return next;
            }
        }
        return NULL;
    }

    Node* _min(){
        if(first==NULL){
            return NULL;
        }
        Node* min = first;
        for(Node* node = first;node!=NULL;node = node->next) {
            if (node->key < min->key) {
                min = node;
            }
        }
        return min;
    }

    Node* _max(){
        if(first==NULL){
            return NULL;
        }
        Node* max = first;
        for(Node* node = first;node!=NULL;node = node->next) {
            if (node->key > max->key) {
                max = node;
            }
        }
        return max;
    }

    Node* _floor(Key key){
        Node* floor = NULL;
        for(Node* node = first;node!=NULL;node = node->next) {
            if (key > node->key && (floor==NULL || floor->key<node->key)){
                floor = node;
            }else if(key = node->key){
                return node;
            }
        }
        return floor;
    }

    Node* _ceiling(Key key){
        Node* ceiling = NULL;
        for(Node* node = first;node!=NULL;node = node->next) {
            if (key < node->key && (ceiling==NULL || ceiling->key>node->key)){
                ceiling = node;
            }else if(key = node->key){
                return node;
            }
        }
        return ceiling;
    }

public:
    SequentialSearchST(){
        first = NULL;
    }

    ~SequentialSearchST(){
        destory(first);
    }

    Value get(Key key){
        Node* node = _get(key);
        return node == NULL?NULL:node->value;
    }

    void put(Key key ,Value value){
        for(Node* node = first;node!=NULL;node = node->next){
            if(node->key==key){
                node->value = value;
                return ;
            }
        }
        first = new Node(key,value,first);
    }

    void remove(Key key){
        Node* pre = NULL;
        for(Node* node = first;node!=NULL;node = node->next){
            if(key == node->key){
                if(node->next == NULL){
                }else if(pre == NULL){
                    first = node->next;
                }else{
                    pre->next = node->next;
                }
                delete node;
                return ;
            }
            pre = node;
        }
        return ;
    }
    bool contains(Key key){
        for(Node* node = first;node!=NULL; node = node->next){
            if(node->key = key){
                return true;
            }
        }
        return false;
    }
    bool isEmpty(){
        return first == NULL;
    }
    int size(){
        int count = 0;
        for(Node* node = first;node!=NULL;node = node->next) {
            count++;
        }
        return count;
    }
    Key min(){
        Node* node = _min();
        return node == NULL?NULL:node->value;
    }
    Key max(){
        Node* node = _max();
        return node == NULL?NULL:node->value;
    }
    Key floor(Key key){
        Node* node = _floor(key);
        return node == NULL?NULL:node->value;
    }//小于等于key的最大值
    Key ceiling(Key key){
        Node* node = _ceiling(key);
        return node == NULL?NULL:node->value;
    }//大于等于key的最小值
    int rank(Key key){
        int rank = 0;
        for(Node* node = first;node!=NULL; node = node->next){
            if(node->key < key){
                rank++;
            }
        }
        return rank;
    }//小于key的数量
    Key select(int k){
        for(Node* node = first;node!=NULL; node = node->next){
            if(rank(node->key)==k){
                return node->key;
            }
        }
        return NULL;
    }//排名为key的键

    void print(string head){
        cout<<head<<":";
        for(Node* node = first;node!=NULL; node = node->next){
                cout << node->key << " ";
        }
        cout << endl;
        return;
    }
};

/**
 * 基于有序数组的二分查找
 * @tparam Key
 * @tparam Value
 */
template <typename Key,typename Value>
class BinarySearchST:public ST<Key,Value>{
private:
   Key* keys;
   Value* values;
   int N;
   int capacity;

   /**
    * 移动[pos,N)区间的数到后一位
    * @param pos
    */
    void _moveToNext(int pos){
       assert(N<capacity);
        for(int n = N;n>pos;n--){
            keys[n] = keys[n-1];
            values[n] = values[n-1];
        }
    }

    /**
    * 移动[pos,N)到前一位
    * @param pos
    */
    void _moveToPre(int pos){
        assert(N<capacity);
        for(int n = pos+1;n<N;n++){
            keys[n-1] = keys[n];
            values[n-1] = values[n];
        }
    }

    /**
    *  [l,h] 范围内寻找key
    * @param key
    * @param l
    * @param h
    */
    int _binaryGetPos(Key key, int low, int h){
        if(h<low)
            return -1;
        int m = (h-low)/2+low;
        if(keys[m] == key){
            return m;
        }else if(keys[m]>key){
            return _binaryGetPos(key,low,m-1);
        }else{
            return _binaryGetPos(key,m+1,h);
        }
    }

public:
    BinarySearchST(int capacity){
        keys = new Key[capacity];
        values = new Value[capacity];
        N = 0;
        this->capacity = capacity;
    }

    ~BinarySearchST(){
        if(keys!=NULL)
            delete keys;
        if(values!=NULL)
            delete values;
    }
    void put(Key key,Value value){
        if(N == capacity){
//            _resize();
            assert(N!=capacity);
        }
        int insert = N;
        for (int i = 0; i < N; ++i) {
            if(key<keys[i]){
                _moveToNext(i);
                insert = i;
                break;
            }else if(key == keys[i]){
                values[i] = value;
                return ;
            }
        }
        keys[insert] = key;
        values[insert] = value;
        N++;
        return ;

    };
    Value get(Key key){
//        assert(contains(key));
//        for (int i = 0; i < N; ++i) {
//            if(key == keys[i]){
//                return values[i];
//            }
//        }
//        return NULL;
        int pos =  _binaryGetPos(key, 0, N);
        if(pos>=0){
            return values[pos];
        }
        return NULL;
    };
    void remove(Key key){
        int pos = _binaryGetPos(key,0,N-1);
        if(pos>=0) {
            _moveToPre(pos);
            N--;
            return;
        }
    };
    bool contains(Key key){
        int pos = _binaryGetPos(key,0,N-1);
        return pos==-1?false:true;
    };
    bool isEmpty(){
        return N == 0;
    };
    int size(){
        return N;
    };
    Key min(){
        assert(N>0);
        return keys[0];
    };
    Key max(){
        assert(N>0);
        return keys[N-1];
    };
    Key floor(Key key){
        Key pre = NULL;
        for (int i = 0; i < N; ++i) {
            if ((keys[i] < key &&(pre == NULL || keys[i] > pre)) || (keys[i] == key)){
                pre = keys[i];
            }
        }
        return pre;
    };//小于等于key的最大值
    Key ceiling(Key key){
        Key pre = NULL;
        for (int i = N-1; i >= 0; --i) {
            if ((keys[i] > key &&(pre == NULL || keys[i] < pre)) || (keys[i] == key)){
                pre = keys[i];
            }
        }
        return pre;
    };//大于等于key的最小值
    int rank(Key key){
        for (int i = 0; i < N; ++i) {
            if (keys[i] >= key) {
               return i;
            }
        }
        return N;
    };//小于key的数量
    Key select(int k){
        return keys[k];
    };//排名为key的键
    void print(string head) {
        cout<<head<<":";
        for (int i = 0; i < N; ++i) {
            cout<<keys[i]<<"-"<<values[i]<<" ";
        }
        cout << endl;
    };

};

int main() {
//    ST<int,int> *st = new SequentialSearchST<int,int>();
    ST<int,int> *st = new BinarySearchST<int,int>(100);

    int n = 20;
    int *arr = TestSortHelper::generateRandomArray(n, 0, n);
//    int *arr = new int[7,3,5,14,4,0,2,15,20,16,13,12];
    TestSortHelper::printArray(arr, n);
    for (int i = 0; i < n ; ++i) {
        st->put(arr[i],arr[i]);
    }
    st->print("after put: ");
    cout<<"get(Key key) " << arr[10] << ":" <<st->get(arr[10])<<endl;
    st->remove(arr[10]);
    st->print("remove(Key key) ");
    cout<<"min() " << ":" <<st->min()<<endl;
    cout<<"max() " << ":" <<st->max()<<endl;
    cout<<"floor(Key key) " << arr[10] << ":" <<st->floor(arr[10])<<endl;
    cout<<"ceiling(Key key) " << arr[10] << ":" <<st->ceiling(arr[10])<<endl;
    cout<<"rank(Key key) " << arr[10] << ":" <<st->rank(arr[10])<<endl;
    cout<<"select(int rank) " << st->rank(arr[10]) << ":" <<st->select(st->rank(arr[10]))<<endl;
    cout<<"size() " << ":" <<st->size()<<endl;
    cout<<"size(Key lo, Key hi) " << 5 << " " << 12 << ":" <<st->size(5,12)<<endl;

    delete arr;
    delete st;
    return 0;
}